package com.github.kezhenxu94.playground.leetcode;

import java.util.Arrays;
import java.util.HashSet;
import java.util.Set;

/**
 *
 * 349. Intersection of Two Arrays
 *
 * Given two arrays, write a function to compute their intersection.
 *
 * Example:
 * Given nums1 = [1, 2, 2, 1], nums2 = [2, 2], return [2].
 *
 * Note:
 * Each element in the result must be unique.
 * The result can be in any order.
 * TODO Optimization
 */
public class Solution349IntersectionOfTwoArrays {

	public static void main(String[] args) {
		Solution349IntersectionOfTwoArrays sol = new Solution349IntersectionOfTwoArrays();
		int[] a1 = {1, 2, 2, 1};
		int[] a2 = {2, 3, 4};
		System.out.println(Arrays.toString(sol.intersection(a1, a2)));
		a1 = new int[]{2, 2, 2};
		a2 = new int[]{3, 3, 3};
		System.out.println(Arrays.toString(sol.intersection(a1, a2)));
	}

	/**
	 * m = array1.length
	 * n = array2.length
	 *
	 * T = O(m x n)
	 */
	public int[] intersection(int[] array1, int[] array2) {
		Set<Integer> result = new HashSet<Integer>();
		for (int e1 : array1)
			for (int e2 : array2)
				if (e1 == e2)
					result.add(e1);
		int[] r = new int[result.size()];
		int i = 0;
		for (int e : result)
			r[i++] = e;
		return r;
	}

}
